| OS | Users | Tasks | Processors |
| MS/PC DOS | S | S | 1 |
| Windows 3x | S | QM | 1 |
| Macintosh System 7.* | S | QM | 1 |
| Windows 9x | S | M* | 1 |
| AmigaDOS | S | M | 1 |
| hline MTS | M | M | 1 |
| UNIX | M | M |  |
| VMS | M | M | 1 |
| NT | S/M | M | |
| Windows 2000 | M | M | |
| BeOS (Hamlet?) | S | M | |
Mark Burgess
October 3, 2001
An operating system is a layer of software which takes care of
technical aspects of a computer's operation.
It shields the user
of the machine from the low-level details of the machine's operation
and provides frequently needed facilities. There is no universal
definition of what an operating system consists of. You can think of
it as being the software which is already installed on a machine,
before you add anything of your own. Normally the operating system has
a number of key elements: (i) a technical layer of software for
driving the hardware of the computer, like disk drives, the keyboard
and the screen; (ii) a filesystem which provides a way of
organizing files logically, and (iii) a simple command
language which enables users to run their own
programs and to manipulate their files in a simple way. Some
operating systems also provide text editors, compilers, debuggers and
a variety of other tools. Since the operating system (OS) is in charge
of a computer, all requests to use its resources and devices need to
go through the OS. An OS therefore provides (iv) legal entry
points
into its code for performing basic operations like writing to devices.
Operating systems may be classified by both how many tasks they can perform `simultaneously' and by how many users can be using the system `simultaneously'. That is: single-user or multi-user and single-task or multi-tasking. A multi-user system must clearly be multi-tasking. The table below shows some examples.
| OS | Users | Tasks | Processors |
| MS/PC DOS | S | S | 1 |
| Windows 3x | S | QM | 1 |
| Macintosh System 7.* | S | QM | 1 |
| Windows 9x | S | M* | 1 |
| AmigaDOS | S | M | 1 |
| hline MTS | M | M | 1 |
| UNIX | M | M | |
| VMS | M | M | 1 |
| NT | S/M | M | |
| Windows 2000 | M | M | |
| BeOS (Hamlet?) | S | M | |
The Macintosh system 7 can be
classified as single-user quasi-multitasking1.1. That means that it is possible to use several user
applications simultaneously. A window manager can simulate the
appearance of several programs running simultaneously, but this relies
on each program obeying specific rules in order to achieve the
illusion. The MacIntosh not a true multitasking system in the sense
that, if one program crashes, the whole system crashes. Windows 
is purported to be preemptive multitasking but most program crashes
also crash the entire system. This might be due to the lack of proper
memory protection. The claim is somewhat confusing.
AmigaDOS is an operating system for the Commodore Amiga computer. It is based on the UNIX model and is a fully multi-tasking, single-user system. Several programs may be actively running at any time. The operating system includes a window environment which means that each independent program has a `screen' of its own and does not therefore have to compete for the screen with other programs. This has been a major limitation on multi-tasking operating systems in the past.
MTS (Michigan timesharing system) was the first time-sharing multi-user system1.2. It supports only simple single-screen terminal based input/output and has no hierarchical file system.
Unix is arguably the most important operating system today, and one which we shall frequently refer to below. It comes in many forms, developed by different manufacturers. Originally designed at AT&T, UNIX split into two camps early on: BSD (Berkeley software distribution) and system 5 (AT&T license). The BSD version was developed as a research project at the university of Berkeley, California. Many of the networking and user-friendly features originate from these modifications. With time these two versions have been merged back together and most systems are now a mixture of both worlds. Historically BSD Unix has been most prevalent in universities, while system 5 has been dominant in business environments. The trend during the last three years by Sun Microsystems and Hewlett-Packard amongst others has been to move towards system 5, keeping only the most important features of the BSD system. A standardization committee for Unix called POSIX, formed by the major vendors, attempts to bring compatibility to the Unix world. Here are some common versions of UNIX.
| Unix | Manufacturer | Mainly BSD / Sys 5 |
| BSD | Berkeley | BSD |
| SunOS (solaris 1) | Sun Microsystems | BSD/sys 5 |
| Solaris 2 | Sun Microsystems | Sys 5 |
| Ultrix | DEC/Compaq | BSD |
| OSF 1/Digital Unix | DEC/Compaq | BSD/sys 5 |
| HPUX | Hewlett-Packard | Sys 5 |
| AIX | IBM | Sys 5 / BSD |
| IRIX | Silicon Graphics | Sys 5 |
| GNU/Linux | Public Domain | Posix (Sys V/BSD) |
| SCO unix | Novell | Sys 5 |
NT is a `new' operating system from Microsoft based on the old VAX/VMS kernel from the Digital Equipment Corporation (VMS's inventor moved to Microsoft) and the Windows32 API. Initially it reinvented many existing systems, but it is gradually being forced to adopt many open standards from the Unix world. It is fully multitasking, and can support multiple users (but only one at a time-- multiple logins by different users is not possible). It has virtual memory and multithreaded support for several processors. NT has a built in object model and security framework which is amongst the most modern in use.
The Be operating system, originally developed for a new multimedia computer called the BeBox, is also new and is a fully multitasking OS. It is optimized for multimedia and is now saleable software developed by Be.Com after the new computer concept failed due to lack of financial backing. BeOS has proper memory protection but allows direct access to video memory (required for fast video games). It also has virtual memory, is pre-emptive multitasking and is based on a microkernel design. Is shares little with Unix except for a Bash shell, a POSIX programming interface and about 150 Unix commands (including Perl).
Before discussing more of the details, let's review some key ideas which lie behind the whole OS idea. Although these ideas may seem simple, you will do well to keep them in mind later. Simple ideas often get lost amongst distracting details, but it is important to remember that the ideas are simple.
A hierarchy is a way of organizing information using levels of detail. The phrase high-level implies few details, whereas low-level implies a lot of detail, down in the guts of things. A hierarchy usually has the form of a tree, which branches from the highest level to the lowest, since each high-level object is composed of several lower-level objects. The key to making large computer programs and to solving difficult problems is to create a hierarchical structure, in which large high-level problems are gradually broken up into manageable low-level problems. Each level works by using a series of `black boxes' (e.g. subroutines) whose inner details are not directly visible. This allows us to hide details and remain sane as the complexity builds up.
This is the single most important concept in computing! It is used repeatedly to organize complex problems.
A computer is not just a box which adds numbers together. It has resources like the keyboard and the screen, the disk drives and the memory. In a multi-tasking system there may be several programs which need to receive input or write output simultaneously and thus the operating system may have to share these resources between several running programs. If the system has two keyboards (or terminals) connected to it, then the OS can allocate both to different programs. If only a single keyboard is connected then competing programs must wait for the resources to become free.
Most multi-tasking systems have only a single central processor unit and yet this is the most precious resource a computer has. An multi-tasking operating system must therefore share cpu-time between programs. That is, it must work for a time on one program, then work a while on the next program, and so on. If the first program was left unfinished, it must then return to work more on that, in a systematic way. The way an OS decides to share its time between different tasks is called scheduling.
The exchange of information is an essential part of computing. Suppose computer A sends a message to computer B reporting on the names of all the users and how long they have been working. To do this it sends a stream of bits across a network. When computer B receives a stream of bits, it doesn't automatically know what they mean. It must decide if the bits represent numbers or characters, integers or floating point numbers, or a mixture of all of them. These different types of data are all stored as binary information - the only difference between them is the way one chooses to interpret them.
The resolution to this problem is to define a protocol. This is a convention or agreement between the operating systems of two machines on what messages may contain. The agreement may say, for instance, that the first thirty-two bits are four integers which give the address of the machine which sent the message. The next thirty-two bits are a special number telling the OS which protocol to use in order to interpret the data. The OS can then look up this protocol and discover that the rest of the data are arranged according to a pattern of
<name><time><name><time>...where the name is a string of bytes, terminated by a zero, and the time is a four byte digit containing the time in hours. Computer B now knows enough to be able to extract the information from the stream of bits.
It is important to understand that all computers have to agree on the way in which the data are sent in advance. If the wrong protocol is diagnosed, then a string of characters could easily be converted into a floating point number - but the result would have been nonsense. Similarly, if computer A had sent the information incorrectly, computer B might not be able to read the data and a protocol error would arise.
For example, when passing parameters to functions in a computer program, there are rules about how the parameter should be declared and in which order they are sent. This is a simple example of a protocol. Protocols are an important part of communication and data typing and they will appear in many forms during our discussion of operating systems.
An operating system is itself a computer program which must be executed. It therefore requires its own share of a computer's resources. This is especially true on multitasking systems, such as UNIX, where the OS is running all the time along side users' programs. Since user programs have to wait for the OS to perform certain services, such as allocating resources, they are slowed down by the OS1.3. The time spent by the OS servicing user requests is called the system overhead. On a multi-user system one would like this overhead to be kept to a minimum, since programs which make many requests of the OS slow not only themselves down, but all other programs which are queuing up for resources.
In the UNIX C-shell (csh) environment, it is possible to find out the
exact fraction of time spent by the OS working on a program's behalf
by using the time function.
Sometimes caching is used more generally to mean `keeping a local copy of data for convenience'.
Here we list the main hardware concepts.
The CPU is driven by a `clock' or pulse generator. Each instruction completes in a certain number of `clock cycles'. Traditionally CPUs are based on CISC (Complex Instruction Set Computing) architecture, where a single instruction takes one or more clock cycles to complete. A new trend is to build RISC (Reduced Instruction Set Computing) processors which aim to be more efficient for a subset of instructions by using redundancy. These have simpler instructions but can execute much more quickly, sometimes with several instructions per clock cycle.
The primary memory is the most important resource a computer has. Since CPUs are only made with instructions for reading and writing to memory, no programs would be able to run without it. There are two types of memory: RAM - random access memory, or read/write memory, which loses its contents when the machine is switched off, and ROM - read only memory, which never loses its contents unless destroyed. ROM is normally used for storing those most fundamental parts of the operating system which are required the instant a computer is switched on, before it knows about disks etc.
Some common logical devices are: the system disks, the keyboard, the screen, the printer and the audio device.
Disks and tapes are often called secondary memory or secondary storage.
Interrupts are hardware signals which are sent to the CPU by the devices it is connected to. These signals literally interrupt the CPU from what it is doing and demand that it spend a few clock cycles servicing a request. For example, interrupts may come from the keyboard because a user pressed a key. Then the CPU must stop what it is doing and read the keyboard, place the key value into a buffer for later reading, and return to what it was doing. Other `events' generate interrupts: the system clock sends interrupts at periodic intervals, disk devices generate interrupts when they have finished an I/O task and interrupts can be used to allow computers to monitor sensors and detectors. User programs can also generate `software interrupts' in order to handle special situations like a `division by zero' error. These are often called traps or exceptions on some systems.
Interrupts are graded in levels. Low level interrupts have a low priority, whereas high level interrupts have a high priority. A high level interrupt can interrupt a low level interrupt, so that the CPU must be able to recover from several `layers' of interruption and end up doing what it was originally doing. This is accomplished by means of a stack or heap1.4. Moreover, programs can often choose whether or not they wish to be interrupted by setting an interrupt mask which masks out the interrupts it does not want to hear about. Masking interrupts can be dangerous, since data can be lost. All systems therefore have non-maskable interrupts for the most crucial operations.
In order to keep track of how the system resources are being used, an OS must keep tables or lists telling it what is free an what is not. For example, data cannot be stored neatly on a disk. As files become deleted, holes appear and the data become scattered randomly over the disk surface.
Spooling is a way of processing data serially. Print jobs are spooled to the printer, because they must be printed in the right order (it would not help the user if the lines of his/her file were liberally mixed together with parts of someone elses file). During a spooling operation, only one job is performed at a time and other jobs wait in a queue to be processed. Spooling is a form of batch processing.
Spooling comes from the need to copy data onto a spool of tape for storage. It has since been dubbed Simultaneous Peripheral Operation On-Line, which is a pretty lousy attempt to make something more meaningful out of the word `spool'!
An important task of an operating system is to provide black-box functions for the most frequently needed operations, so that users do not have to waste their time programming very low level code which is irrelevant to their purpose. These ready-made functions comprise frequently used code and are called system calls.
For example, controlling devices requires very careful and complex programming. Users should not have to write code to position the head of the disk drive at the right place just to save a file to the disk. This is a very basic operation which everyone requires and thus it becomes the responsibility of the OS. Another example is mathematical functions or graphics primitives.
System calls can be thought of as a very simple protocol - an agreed way of asking the OS to perform a service. Some typical OS calls are: read, write (to screen, disk, printer etc), stat (get the status of a file: its size and type) and malloc (request for memory allocation).
On older microcomputers, where high level languages are uncommon, system calls are often available only through assembler or machine code. On modern systems and integrated systems like UNIX, they are available as functions in a high level language like C.
Commands like
dir ; list files (DOS) ls ; list files (UNIX) cd ; change directory copy file prn ; copy file to printer myprog ; execute program `myprog'constitute a basic command language. Every computer must have such a language (except perhaps the Macintosh - yawn!). In microcomputer operating systems the command language is often built into the system code, whereas on larger systems (UNIX) the commands are just executable programs like the last example above.
The command language deals typically with: file management, process management and text editing.
In creating a system to store files we must answer some basic questions.
Multitasking cannot be fully exploited if each user has only one output terminal (screen). Each interactive program needs its own screen and keyboard1.5. There are three solutions to this problem:
![$[1]$](A short introduction to operating systems_files/img50000.png){kind=small}
), it requires a considerable amount of
memory and CPU power to implement. The problem of overlapping windows
requires there to be a manager which controls the sharing of space
on the screen. All of the graphics must be drawn and redrawn continuously.
The operating system must provide primitives for doing this.
We shall not consider windowing further in this text, but it is worth bearing in mind that the principles are very similar to those of operating systems. Sharing and management are the key concepts.
Before proceeding, you should note that the design of operating systems is an active area of research. There are no universal solutions to the issues that we shall discuss, rather OS design must be thought of as a study of compromises. Hopefully you will get a feel for this during the course of the tutorial.
Before tackling the complexities of multi-tasking, it is useful to
think about the operation of a single-task OS without all the clutter
that multi-tasking entails. In a multi-task OS the features we shall
discuss below have to be reproduced 
-times and then augmented by
extra control structures.
The key elements of a single-task computer are shown in figure 2.1. Roughly speaking, at the hardware level a computer consists of a CPU, memory and a number of peripheral devices. The CPU contains registers or `internal variables' which control its operation. The CPU can store information only in the memory it can address and in the registers of other microprocessors it is connected to. The CPU reads machine code instructions, one at a time, from the memory and executes them forever without stopping.
Here is a brief summary of the types of register a CPU has. Some microprocessors have several of each type.
| Register | Purpose |
| Accumulator | Holds the data currently being worked on. |
| Program counter | Holds the address of the next instruction |
| to be executed | |
| Index (addressing) registers | Used to specify the address of data to be loaded into or |
| saved from the accumulator, or operated on in some way. | |
| Stack pointer | Points to the top of the CPUs |
| own hardware controlled stack. | |
| Status register | Contains status information after each instruction |
| which can be tested for to detect errors etc. |
The memory, as seen by the CPU, is a large string of bytes starting
with address 
and increasing up to the maximum address. Physically
it is made up, like a jigsaw puzzle, of many memory chips and control
chips. mapped into the diagram shown. Normally, because of the
hardware design of the CPU, not all of the memory is available to the
user of the machine. Some of it is required for the operation of the
CPU.
The roughly distinguished areas in figure 2.1 are
 |
A stack is a so-called last-in first-out (LIFO) data structure. That is to say - the last thing to be placed on top of a stack, when making it, is the first item which gets removed when un-making it. Stacks are used by the CPU to store the current position within a program before jumping to subroutines, so that they remember where to return to after the subroutine is finished. Because of the nature of the stack, the CPU can simply deposit the address of the next instruction to be executed (after the subroutine is finished) on top of the stack. When the subroutine is finished, the CPU pulls the first address it finds off the top of the stack and jumps to that location.
Notice that the stack mechanism will continue to work even if the subroutine itself calls another subroutine, since the second subroutine causes another stack frame to be saved on the top of the stack. When that is finished, it returns to the first subroutine and then to the original program in the correct order.
On many older microcomputers and in many operating systems the stack is allocated with a fixed size in advance. If too many levels of nested subroutines are called, the stack can overflow. Consider the following example code for a stack.
//
// A simple stack handler.
//
// Use the commands "push" and "pop" to push onto the stack and to pop
// "out" of the stack. The allocated stacksize is very small so that
// an overflow can occur if you push too far!! e.g. input
//
// push 23
// push 4
// pop
// push 678
// quit
//
// In a real stack handler the numbers would be the address of the next
// instruction to return to after completing a subroutine.
//
// The program is compiled with
//
// g++ stack.C
//
// MB 1994
//
//*********************************************************************
#include <iostream.h>
#include <strstream.h>
#include <string.h>
//**********************************************************************
// Include file
//**********************************************************************
const int forever = 1;
const int stacksize = 10;
const int bufsize = 20;
//**********************************************************************
class Stack
{
public:
int stack[stacksize];
Stack();
void ShowStack();
void Push(int);
int Pop();
private:
int stackpointer;
};
//**********************************************************************
// Level 0
//**********************************************************************
main ()
{ char input[bufsize];
char command[5];
int number, newnumber;
Stack s;
cout << "Stack demo\n\n";
s.ShowStack();
while (forever)
{
cout << "Enter command: ";
// Extract command
cin.getline(input,bufsize);
istrstream(input,sizeof(input)) >> command >> number;
// Interpret command
if (strcmp(command,"push") == 0)
{
s.Push(number);
}
else if (strcmp(command,"pop")==0)
{
newnumber = s.Pop();
}
else if (strcmp(command,"quit")==0)
{
break;
}
else
{
number = 0;
cout << "Bad command\n\n";
}
s.ShowStack();
}
s.ShowStack();
}
//**********************************************************************
// Class Stack
//**********************************************************************
Stack::Stack()
{ int i;
stackpointer = 0;
for (i = 0; i < stacksize; i++)
{
stack[i] = 0;
}
}
//**********************************************************************
void Stack::Push (int n)
{
cout << "Pushing " << n << " on the stack\n";
if (stackpointer >= stacksize)
{
cerr << "Stack overflow!\n";
return;
}
stack[stackpointer] = n;
stackpointer++;
}
//**********************************************************************
int Stack::Pop ()
{
if (stackpointer == 0)
{
cerr << "Stack underflow!\n";
return 0;
}
stackpointer--;
cout << "Popped " << stack[stackpointer] << " from stack\n";
return (stack[stackpointer]);
}
//**********************************************************************
void Stack::ShowStack ()
{ int i;
for (i = stacksize-1; i >= 0; i--)
{
cout << "stack[" << i << "] = " << stack[i];
if (i == stackpointer)
{
cout << " <<-- Pointer\n";
}
else
{
cout << endl;
}
}
}
In this example, only numbers are stored. At the hardware level, this kind of stack is used by the CPU to store addresses and registers during machine-code subroutine jumps. Operating systems also use software controlled stacks during the execution of users' programs. High level languages subroutines can have local variables which are also copied to the stack as one large stack frame during the execution of subroutines.
Input arrives at the computer at unpredictable intervals. The system must be able to detect its arrival and respond to it.
Interrupts are hardware triggered signals which cause the CPU to stop what it is doing and jump to a special subroutine. Interrupts normally arrive from hardware devices, such as when the user presses a key on the keyboard, or the disk device has fetched some data from the disk. They can also be generated in software by errors like division by zero or illegal memory address.
When the CPU receives an interrupt, it saves the contents of its registers on the hardware stack and jumps to a special routine which will determine the cause of the interrupt and respond to it appropriately. Interrupts occur at different levels. Low level interrupts can be interrupted by high level interrupts. Interrupt handling routines have to work quickly, or the computer will be drowned in the business of servicing interrupts. For certain critical operations, low level interrupts can be ignored by setting a mask (See also the generalization of this for multiuser systems in chapter 4).
There is no logical difference between what happens during the execution of an interrupt routine and a subroutine. The difference is that interrupt routines are triggered by events, whereas software subroutines follow a prearranged plan.
An important area is the interrupt vector. This is a region of memory reserved by the hardware for servicing of interrupts. Each interrupt has a number from zero to the maximum number of interrupts supported on the CPU; for each interrupt, the interrupt vector must be programmed with the address of a routine which is to be executed when the interrupt occurs. i.e. when an interrupt occurs, the system examines the address in the interrupt vector for that interrupt and jumps to that location. The routine exits when it meets an RTI (return from interrupt) instruction.
The CPU and the devices attached to it do not work at the same speed. Buffers are therefore needed to store incoming or outgoing information temporarily, while it is waiting to be picked up by the other party. A buffer is simply an area of memory which works as a waiting area. It is a first-in first-out (FIFO) data structure or queue.
To start an I/O operation, the CPU writes appropriate values into the registers of the device controller. The device controller acts on the values it finds in its registers. For example, if the operation is to read from a disk, the device controller fetches data from the disk and places it in its local buffer. It then signals the CPU by generating an interrupt.
While the CPU is waiting for the I/O to complete it may do one of two things. It can do nothing or idle until the device returns with the data (synchronous I/O), or it can continue doing something else until the completion interrupt arrives (asynchronous I/O). The second of these possibilities is clearly much more efficient.
Very high speed devices could place heavy demands on the CPU for I/O servicing if they relied on the CPU to copy data word by word. The DMA controller is a device which copies blocks of data at a time from one place to the other, without the intervention of the CPU. To use it, its registers must be loaded with the information about what it should copy and where it should copy to. Once this is done, it generates an interrupt to signal the completion of the task. The advantage of the DMA is that it transfers large amounts of data before generating an interrupt. Without it, the CPU would have to copy the data one register-full at a time, using up hundreds or even thousands of interrupts and possibly bringing a halt to the machine!
To make a multi-tasking OS we need loosely to reproduce all of the features discussed in the last chapter for each task or process which runs. It is not necessary for each task to have its own set of devices. The basic hardware resources of the system are shared between the tasks. The operating system must therefore have a `manager' which shares resources at all times. This manager is called the `kernel' and it constitutes the main difference between single and multitasking operating systems.
On a multi-user system it is important that one user should not be able to interfere with another user's activities, either purposefully or accidentally. Certain commands and system calls are therefore not available to normal users directly. The super-user is a privileged user (normally the system operator) who has permission to do anything, but normal users have restrictions placed on them in the interest of system safety.
For example: normal users should never be able to halt the system; nor should they be able to control the devices connected to the computer, or write directly into memory without making a formal request of the OS. One of the tasks of the OS is to prevent collisions between users.
It is crucial for the security of the system that different tasks, working side by side, should not be allowed to interfere with one another (although this occasionally happens in microcomputer operating systems, like the Macintosh, which allow several programs to be resident in memory simultaneously). Protection mechanisms are needed to deal with this problem. The way this is normally done is to make the operating system all-powerful and allow no user to access the system resources without going via the OS.
To prevent users from tricking the OS, multiuser systems are based on hardware which supports two-mode operation: privileged mode for executing OS instructions and user mode for working on user programs. When running in user mode a task has no special privileges and must ask the OS for resources through system calls. When I/O or resource management is performed, the OS takes over and switches to privileged mode. The OS switches between these modes personally, so provided it starts off in control of the system, it will alway remain in control.
To prevent users from gaining control of devices, by tricking the OS, a mechanism is required to prevent them from writing to an arbitrary address in the memory. For example, if the user could modify the OS program, then it would clearly be possible to gain control of the entire system in privileged mode. All a user would have to do would be to change the addresses in the interrupt vector to point to a routine of their own making. This routine would then be executed when an interrupt was received in privileged mode.
The solution to this problem is to let the OS define a segment of memory for each user process and to check, when running in user mode, every address that the user program refers to. If the user attempts to read or write outside this allowed segment, a segmentation fault is generated and control returns to the OS. This checking is normally hard-wired into the hardware of the computer so that it cannot be switched off. No checking is required in privileged mode.
//******************************************************************
//
// Example of a segmentation fault in user mode
//
//******************************************************************
main() // When we start, we are by definition in user mode.
{ int *ptr;
ptr = 0; // An address guaranteed to NOT be in our segment.
cout << *ptr;
}
We can represent a multi-tasking system schematically as in figure 3.1. Clearly the memory map of a computer does not look like this figure. It looks like the figures in the previous chapter, so the OS has to simulate this behaviour using software. The point of this diagram is only that it shows the elements required by each process executing on the system.
Each program must have a memory area to work in and a stack to keep track of subroutine calls and local variables.Each program must have its own input/output sources. These cannot be the actual resources of the system: instead, each program has a virtual I/O stream. The operating system arranges things so that the virtual I/O looks, to the user program, as though it is just normal I/O. In reality, the OS controls all the I/O itself and arranges the sharing of resources transparently. The virtual output stream for a program might be a window on the real screen, for instance. The virtual printer is really a print-queue. The keyboard is only `connected' to one task at a time, but the OS can share this too. For example, in a window environment, this happens when a user clicks in a particular window.
So far we have talked about the OS almost as though it were a living thing. In a multitasking, multi-user OS like UNIX this is not a bad approximation to the truth! In what follows we make use of UNIX terminology and all of the examples we shall cover later will refer to versions of the UNIX operating system.
The part of the OS which handles all of the details of sharing and device handling is called the kernel or core. The kernel is not something which can be used directly, although its services can be accessed through system calls. What is needed is a user interface or command line interface (CLI) which allows users to log onto the machine and manipulate files, compile programs and execute them using simple commands. Since this is a layer of software which wraps the kernel in more acceptable clothes, it is called a shell around the kernel.
It is only by making layers of software, in a hierachy that very complex programs can be written and maintained. The idea of layers and hierarchies returns again and again.
The UNIX kernel is a very large program, but it does not perform all of the services required in an OS. To keep the size of the kernel to a minimum, it only deals with the sharing of resources. Other jobs for operating system (which we can call services) are implemented by writing program which run along side user's programs. Indeed, they are just `user programs' - the only difference is that are owned by the system. These programs are called daemons. Here are some example from UNIX.
We shall consider this in more detail in later chapters. For now it is useful to keep in mind that multiprocessors are an important element of modern OS design.
operator operand load 12 add 23 store 1334 jsr 5678 wait 1 fork 0etc. Read in the commands and print out a log of what the commands are, in the form "Executing (operator) on (operand)". You should be able to recognize the commands `wait' and `fork' specially, but the other commands may be anything you like. The aim is to simulate the type of commands a real program has to execute.
Multitasking and multi-user systems need to distinguish between the different programs being executed by the system. This is accomplished with the concept of a process.
Before talking about process management we shall introduce some of the names which are in common use. Not all operating systems or books agree on the definitions of these names. In this chapter we shall take a liberal attitude - after all, it is the ideas rather than the names which count. Try to remember the different terms - they will be used repeatedly.
On most multitasking systems, only one process can truly be active at
a time - the system must therefore
share its time between the execution of many
processes. This sharing is called scheduling.
(Scheduling
time management.)
Different methods of scheduling are appropriate for different kinds of execution. A queue is one form of scheduling in which each program waits its turn and is executed serially. This is not very useful for handling multitasking, but it is necessary for scheduling devices which cannot be shared by nature. An example of the latter is the printer. Each print job has to be completed before the next one can begin, otherwise all the print jobs would be mixed up and interleaved resulting in nonsense.
We shall make a broad distinction between two types of scheduling:
To choose an algorithm for scheduling tasks we have to understand what it is we are trying to achieve. i.e. What are the criterea for scheduling?
Some of these criterea cannot be met simultaneously and we must make compromises. In particular, what is good for batch jobs is often not good for interactive processes and vice-versa, as we remark under Run levels - priority below.
For example, in UNIX the long term scheduler moves processes which have been sleeping for more than a certain time out of memory and onto disk, to make space for those which are active. Sleeping jobs are moved back into memory only when they wake up (for whatever reason). This is called swapping.
The most complex systems have several levels of scheduling and exercise different scheduling polices for processes with different priorities. Jobs can even move from level to level if the circumstances change.
Rather than giving all programs equal shares of CPU time, most systems have priorities. Processes with higher priorities are either serviced more often than processes with lower priorities, or they get longer time-slices of the CPU.
Priorities are not normally fixed but vary according to the performance of the system and the amount of CPU time a process has already used up in the recent past. For example, processes which have used a lot of CPU time in the recent past often have their priority reduced. This tends to favour iterative processes which wait often for I/O and makes the response time of the system seem faster for interactive users.
In addition, processes may be reduced in priority if their total accumulated CPU usage becomes very large. (This occurs, for example in UNIX). The wisdom of this approach is arguable, since programs which take a long time to complete tend to be penalized. Indeed, they take must longer to complete because their priority is reduced. If the priority continued to be lowered, long jobs would never get finished. This is called process starvation and must be avoided.
Scheduling algorithms have to work without knowing how long processes
will take. Often the best judge of how demanding a program will be is
the user who started the program. UNIX allows users to reduce the
priority of a program themselves using the nice command.
`Nice' users are supposed to sacrifice their own self-interest for
the good of others. Only the system manager can increase the
priority of a process.
Another possibility which is often not considered, is that of increasing the priority of resource-gobbling programs in order to get them out of the way as fast as possible. This is very difficult for an algorithm to judge, so it must be done manually by the system administrator.
Switching from one running process to another running process incurs a cost to the system. The values of all the registers must be saved in the present state, the status of all open files must be recorded and the present position in the program must be recorded. Then the contents of the MMU must be stored for the process (see next chapter). Then all those things must be read in for the next process, so that the state of the system is exactly as it was when the scheduler last interrupted the process. This is called a context switch. Context switching is a system overhead. It costs real time and CPU cycles, so we don't want to context switch too often, or a lot of time will be wasted.
The state of each process is saved to a data structure in the kernel called a process control block (PCB). Here is an example PCB from Mach OS:
typedef struct machpcb
{
char mpcb_frame[REGOFF];
struct regs mpcb_regs; /* user's saved registers */
struct rwindow mpcb_wbuf[MAXWIN]; /* user window save buffer */
char *mpcb_spbuf[MAXWIN]; /* sp's for each wbuf */
int mpcb_wbcnt; /* number of saved windows in pcb_wbuf */
struct v9_fpu *mpcb_fpu; /* fpu state */
struct fq mpcb_fpu_q[MAXFPQ]; /* fpu exception queue */
int mpcb_flags; /* various state flags */
int mpcb_wocnt; /* window overflow count */
int mpcb_wucnt; /* window underflow count */
kthread_t *mpcb_thread; /* associated thread */
}
machpcb_t;
Below is a kernel process structure for a UNIX system.
struct proc
{
struct proc *p_link; /* linked list of running processes */
struct proc *p_rlink;
struct proc *p_nxt; /* linked list of allocated proc slots */
struct proc **p_prev; /* also zombies, and free procs */
struct as *p_as; /* address space description */
struct seguser *p_segu; /* "u" segment */
caddr_t p_stack; /* kernel stack top for this process */
struct user *p_uarea; /* u area for this process */
char p_usrpri; /* user-priority based on p_cpu and p_nice */
char p_pri; /* priority, negative is high */
char p_cpu; /* (decayed) cpu usage solely for scheduling */
char p_stat;
char p_time; /* seconds resident (for scheduling) */
char p_nice; /* nice for cpu usage */
char p_slptime; /* seconds since last block (sleep) */
char p_cursig;
int p_sig; /* signals pending to this process */
int p_sigmask; /* current signal mask */
int p_sigignore; /* signals being ignored */
int p_sigcatch; /* signals being caught by user */
int p_flag;
uid_t p_uid; /* user id, used to direct tty signals */
uid_t p_suid; /* saved (effective) user id from exec */
gid_t p_sgid; /* saved (effective) group id from exec */
short p_pgrp; /* name of process group leader */
short p_pid; /* unique process id */
short p_ppid; /* process id of parent */
u_short p_xstat; /* Exit status for wait */
short p_cpticks; /* ticks of cpu time, used for p_pctcpu */
struct ucred *p_cred; /* Process credentials */
struct rusage *p_ru; /* mbuf holding exit information */
int p_tsize; /* size of text (clicks) */
int p_dsize; /* size of data space (clicks) */
int p_ssize; /* copy of stack size (clicks) */
int p_rssize; /* current resident set size in clicks */
int p_maxrss; /* copy of u.u_limit[MAXRSS] */
int p_swrss; /* resident set size before last swap */
caddr_t p_wchan; /* event process is awaiting */
long p_pctcpu; /* (decayed) %cpu for this process */
struct proc *p_pptr; /* pointer to process structure of parent */
struct proc *p_cptr; /* pointer to youngest living child */
struct proc *p_osptr; /* pointer to older sibling processes */
struct proc *p_ysptr; /* pointer to younger siblings */
struct proc *p_tptr; /* pointer to process structure of tracer */
struct itimerval p_realtimer;
struct sess *p_sessp; /* pointer to session info */
struct proc *p_pglnk; /* list of pgrps in same hash bucket */
short p_idhash; /* hashed based on p_pid for kill+exit+... */
short p_swlocks; /* number of swap vnode locks held */
struct aiodone *p_aio_forw; /* (front)list of completed asynch IO's */
struct aiodone *p_aio_back; /* (rear)list of completed asynch IO's */
int p_aio_count; /* number of pending asynch IO's */
int p_threadcnt; /* ref count of number of threads using proc */
int p_cpuid; /* processor this process is running on */
int p_pam; /* processor affinity mask */
};
UNIX also uses a `user' structure to keep auxiliary information which
is only needed when jobs are not `swapped out' (see next chapter).
One of the benefits of multitasking is that several processes can be made to cooperate in order to achieve their ends. To do this, they must do one of the following.
As soon as we open the door to co-operation there is a problem of how to synchronize cooperating processes. For example, suppose two processes modify the same file. If both processes tried to write simultaneously the result would be a nonsensical mixture. We must have a way of synchronizing processes, so that even concurrent processes must stand in line to access shared data serially.
Synchronization is a tricky problem in multiprocessor systems, but it can be achieved with the help of critical sections and semaphores/ locks. We shall return to these below.
The creation of a process requires the following steps. The order in which they are carried out is not necessarily the same in all cases.
In a democratic system anyone can choose to start a new process, but it is never users which create processes but other processes! That is because anyone using the system must already be running a shell or command interpreter in order to be able to talk to the system, and the command interpreter is itself a process.
When a user creates a process using the command interpreter, the new process become a child of the command interpreter. Similarly the command interpreter process becomes the parent for the child. Processes therefore form a hierarchy.
The processes are linked by a tree structure. If a parent is signalled or killed, usually all its children receive the same signal or are destroyed with the parent. This doesn't have to be the case--it is possible to detach children from their parents--but in many cases it is useful for processes to be linked in this way.
When a child is created it may do one of two things.
As an example of process creation, we shall consider UNIX. The following
example program is written in C++ and makes use of the standard
library function fork(). The syntax of fork is
returncode = fork();When this instruction is executed, the process concerned splits into two and both continue to execute independently from after the
fork
intruction. If fork is successful, it returns to the child process
and the process identifier or pid of the child process to the
parent. It, for some reason, a new process cannot be created it
returns a value of 
to the parent.
The following example does not check for errors if fork fails.
//**************************************************************
//*
//* A brief demo of the UNIX process duplicator fork().
//*
//* g++ unix.C to compile this.
//*
//**************************************************************
#include <iostream.h>
extern "C" void sleep();
extern "C" int fork();
extern "C" int getpid();
extern "C" void wait();
extern "C" void exit();
void ChildProcess();
//***************************************************************
main ()
{ int pid, cid;
pid = getpid();
cout << "Fork demo! I am the parent (pid = " << pid << ")\n";
if (! fork())
{
cid = getpid();
cout << "I am the child (cid=" << cid << ") of (pid = " << pid << ")\n";
ChildProcess();
exit(0);
}
cout << "Parent waiting here for the child...\n";
wait(NULL);
cout << "Child finished, parent quitting too!\n";
}
//**************************************************************
void ChildProcess()
{ int i;
for (i = 0; i < 10; i++)
{
cout << i << "..\n";
sleep(1);
}
}
Here is the output from the program in a test run. Note that the parent and child processes share the same output stream, so we see how they are synchronised from the order in which the output is mixed.
Fork demo! I am the parent (pid = 2196) I am the child (cid=2197) of (pid = 2196) 0.. Parent waiting here for the child... 1.. 2.. 3.. 4.. 5.. 6.. 7.. 8.. 9.. Child finished, parent quitting too!
Note that the child has time to execute its first instruction before
the parent has time to call wait(), so the zero appears
before the message from the parent. When the child goes to sleep for
one second, the parent catches up.
In order to know when to execute a program and when not to execute a program, it is convenient for the scheduler to label programs with a `state' variable. This is just an integer value which saves the scheduler time in deciding what to do with a process. Broadly speaking the state of a process may be one of the following.
| From state | Event | To state |
| New | Accepted | Ready |
| Ready | Scheduled / Dispatch | Running |
| Running | Need I/O | Waiting |
| Running | Scheduler timeout | Ready |
| Running | Completion / Error / Killed | Terminated |
| Waiting | I/O completed or wakeup event | Ready |
The basis of all scheduling is the queue structure. A round-robin scheduler uses a queue but moves cyclically through the queue at its own speed, instead of waiting for each task in the queue to complete. Queue scheduling is primarily used for serial execution.
There are two main types of queue.
The efficiency of the two schemes is subjective: long jobs have to wait longer if short jobs are moved in front of them, but if the distribution of jobs is random then we can show that the average waiting time of any one job is shorter in the SJF scheme, because the greatest number of jobs will always be executed in the shortest possible time.
Of course this argument is rather stupid, since it is only the system which cares about the average waiting time per job, for its own prestige. Users who print only long jobs do not share the same clinical viewpoint. Moreover, if only short jobs arrive after one long job, it is possible that the long job will never get printed. This is an example of starvation. A fairer solution is required (see exercises below).
Queue scheduling can be used for CPU scheduling,
but it is quite inefficient.
To understand why simple queue scheduling is not desirable we can begin
by looking at a diagram which shows how the CPU and the devices are
being used when a FCFS queue is used.
We label each process by 
, 
... etc. A blank space indicates that
the CPU or I/O devices are in an idle state (waiting for a customer).
| CPU | |
- | |
- | |
- |
| devices | - | |
- | |
- | |
This diagram shows that starts out with a CPU burst. At some
point it needs input (say from a disk)
and sends a request to the device. While
the device is busy servicing the request from , the CPU is
idle, waiting for the result. Similarly, when the result returns,
the device waits idle while the next CPU burst takes place. When
is finished, is started and goes through the same kind of cycle.
There are many blank spaces in the diagram, where the devices and the
CPU are idle. Why, for example, couldn't the device be searching
for the I/O for while the CPU was busy with and vice versa?
We can improve the picture by introducing a new rule: every time
one process needs to wait for a device, it gets put to the back of
the queue. Now consider the following diagram, in which we have three
processes. They will always be scheduled in order , , 
until
one or all of them is finished.
| CPU | |
|
|
|
-finishes |
|
-finishes |
|
- | |
| devices | - | |
|
|
|
- | |
- | |
- |
starts out as before with a CPU burst. But now when it occupies
the device, takes over the CPU. Similarly when has to wait
for the device to complete its I/O, gets executed, and when
has to wait, takes over again. Now suppose finishes:
takes over, since it is next in the queue, but now the device
is idle, because did not need to use the device. Also, when
finishes, only is left and the gaps of idle time get bigger.
In the beginning, this second scheme looked pretty good - both the CPU and the devices were busy most of the time (few gaps in the diagram). As processes finished, the efficiency got worse, but on a real system, someone will always be starting new processes so this might not be a problem.
Let us ask - how can we improve this scheme? The resource utilization is not too bad, but the problem is that it assumes that every program goes in a kind of cycle
If one program spoils this cycle by performing a lot of CPU intensive work, or by waiting for dozens of I/O requests, then the whole scheme goes to pieces.
The use of the I/O - CPU burst cycle to requeue jobs improves the resource utilization considerably, but it does not prevent certain jobs from hogging the CPU. Indeed, if one process went into an infinite loop, the whole system would stop dead. Also, it does not provide any easy way of giving some processes priority over others.
A better solution is to ration the CPU time, by introducing time-slices. This means that
The time-sharing is implemented by a hardware timer. On each context switch, the system loads the timer with the duration of its time-slice and hands control over to the new process. When the timer times-out, it interrupts the CPU which then steps in and switches to the next process.
The basic queue is the FCFS/FIFO queue. New processes are added to the end, as are processes which are waiting.
The success or failure of round-robin (RR) scheduling depends on the length of the time-slice or time-quantum. If the slices are too short, the cost of context switching becomes high in comparision to the time spent doing useful work. If they become too long, processes which are waiting spend too much time doing nothing - and in the worst case, everything reverts back to FCFS. A rule of thumb is to make the time-slices large enough so that only, say, twenty percent of all context switches are due to timeouts - the remainder occur freely because of waiting for requested I/O.
Many multiuser systems allow restrictions to be placed on user activity. For example, it is possible to limit the CPU time used by any one job. If a job exceeds the limit, it is terminated by the kernel. In order to make such a decision, the kernel has to keep detailed information about the cumulative use of resources for each process. This is called accounting and it can be a considerable system overhead. Most system administrators would prefer not to use accounting - though unfortunately many are driven to it by thoughtless or hostile users.
Threads, sometimes called lightweight processes (LWPs) are indepedendently scheduled parts of a single program. We say that a task is multithreaded if it is composed of several independent subprocesses which do work on common data, and if each of those pieces could (at least in principle) run in parallel.
If we write a program which uses threads - there is only one program, one executable file, one task in the normal sense. Threads simply enable us to split up that program into logically separate pieces, and have the pieces run independently of one another, until they need to communicate. In a sense, threads are a further level of object orientation for multitasking systems. They allow certain functions to be executed in parallel with others.
 |
On a truly parallel computer (several CPUs) we might imagine parts of a program (different subroutines) running on quite different processors, until they need to communicate. When one part of the program needs to send data to the other part, the two independent pieces must be synchronized, or be made to wait for one another. But what is the point of this? We can always run independent procedures in a program as separate programs, using the process mechanisms we have already introduced. They could communicate using normal interprocesses communication. Why introduce another new concept? Why do we need threads?
The point is that threads are cheaper than normal processes, and that they can be scheduled for execution in a user-dependent way, with less overhead. Threads are cheaper than a whole process because they do not have a full set of resources each. Whereas the process control block for a heavyweight process is large and costly to context switch, the PCBs for threads are much smaller, since each thread has only a stack and some registers to manage. It has no open file lists or resource lists, no accounting structures to update. All of these resources are shared by all threads within the process. Threads can be assigned priorities - a higher priority thread will get put to the front of the queue.
Let's define heavy and lightweight processes with the help of a table.
| Object | Resources |
| Thread (LWP) | Stack  set of CPU registers CPU time. |
| Task (HWP) | 1 thread process control block, |
| program code, memory segment etc. | |
| Multithreaded task | n-threads process control block, |
| program code, memory segment etc. |
From our discussion of scheduling, we can see that the sharing of resources could have been made more effective if the scheduler had known exactly what each program was going to do in advance. Of course, the scheduling algorithm can never know this - but the programmer who wrote the program does know. Using threads it is possible to organize the execution of a program in such a way that something is always being done, when ever the scheduler gives the heavyweight process CPU time.
In modern operating systems, there are two levels at which threads operate: system or kernel threads and user level threads. If the kernel itself is multithreaded, the scheduler assigns CPU time on a thread basis rather than on a process basis. A kernel level thread behaves like a virtual CPU, or a power-point to which user-processes can connect in order to get computing power. The kernel has as many system level threads as it has CPUs and each of these must be shared between all of the user-threads on the system. In other words, the maximum number of user level threads which can be active at any one time is equal to the number of system level threads, which in turn is equal to the number of CPUs on the system.
Since threads work ``inside'' a single task, the normal process scheduler cannot normally tell which thread to run and which not to run - that is up to the program. When the kernel schedules a process for execution, it must then find out from that process which is the next thread it must execute. If the program is lucky enough to have more than one processor available, then several threads can be scheduled at the same time.
Some important implementations of threads are
Threads are of obvious importance in connection with parallel processing. There are two approaches to scheduling on a multiprocessor machine:
The POSIX standardization organization has developed a standard set of function calls for use of user-level threads. This library is called the pthread interface.
Let's look at an example program which counts the number of lines in a list of files. This program will serve as an example for the remainder of this chapter. We shall first present the program without threads, and then rewrite it, starting a new thread for each file. The threaded version of the program has the possibility of reading several of the files in parallel and is in principle more efficient, whereas the non-threaded version must read the files sequentially.
The non-threaded version of the program looks like this:
//
// Count the number of lines in a number of files, non threaded
// version.
//
////////////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <fstream.h>
const int bufsize = 100;
void ParseFile(char *);
int LINECOUNT = 0;
/**********************************************************************/
main ()
{
cout << "Single threaded parent...\n";
ParseFile("proc1");
ParseFile("proc2");
ParseFile("proc3");
ParseFile("proc4");
cout << "Number of lines = %d\n",LINECOUNT;
}
/**********************************************************************/
void ParseFile(char *filename)
{ fstream file;
char buffer[bufsize];
cout << "Trying to open " << filename << endl;
file.open(filename, ios::in);
if (! file)
{
cerr << "Couldn't open file\n";
return;
}
while (!file.eof())
{
file.getline(buffer,bufsize);
cout << filename << ":" <<buffer << endl;
LINECOUNT++;
}
file.close();
}
This program calls the function ParseFile() several times
to open and count the number of lines in a series of files.
The number of lines is held in a global variable called
LINECOUNT. A global variable is, by definition, shared
data. This will cause a problem when we try to parallelize
the program using threads.
Here is the threaded version:
//
// Count the number of lines in a number of files.
// Illustrates use of multithreading. Note: run this program
// several times to see how the threads get scheduled on the system.
// Scheduling will be different each time since the system has lots
// of threads running, which we do not see and these will affect the
// scheduling of our program.
//
// Note that, on a multiprocessor system, this program has a potential
// race condition to update the shared variable LINECOUNT, so we
// must use a mutex to make a short critical section whenever accessing
// this shared variable.
//
// This program uses POSIX threads (pthreads)
//
///////////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <fstream.h>
#include <pthread.h>
#include <sched.h>
const int bufsize = 100;
const int maxfiles = 4;
void *ParseFile(char *); // Must be void *, defined in pthread.h !
int LINECOUNT = 0;
pthread_mutex_t MUTEX = PTHREAD_MUTEX_INITIALIZER;
/**********************************************************************/
main ()
{ pthread_t tid[maxfiles];;
int i,ret;
// Create a thread for each file
ret = pthread_create(&(tid[0]), NULL, ParseFile,"proc1");
ret = pthread_create(&(tid[1]), NULL, ParseFile,"proc2");
ret = pthread_create(&(tid[2]), NULL, ParseFile,"proc3");
ret = pthread_create(&(tid[3]), NULL, ParseFile,"proc4");
cout << "Parent thread waiting...\n";
// If we don't wait for the threads, they will be killed
// before they can start...
for (i = 0; i < maxfiles; i++)
{
ret = pthread_join(tid[i],(void **)NULL);
}
cout << "Parent thread continuing\n";
cout << "Number of lines = " << LINECOUNT << endl;
}
/**********************************************************************/
void *ParseFile(char *filename)
{ fstream file;
char buffer[bufsize];
int ret;
cout << "Trying to open " << filename << endl;
file.open(filename, ios::in);
if (! file)
{
cerr << "Couldn't open file\n";
return NULL;
}
while (!file.eof())
{
file.getline(buffer,bufsize);
cout << filename << ":" <<buffer << endl;
// Critical section
ret = pthread_mutex_lock(&MUTEX);
LINECOUNT++;
ret = pthread_mutex_unlock(&MUTEX);
// Try uncommenting this ....
// Yield the process, to allow next thread to be run
// sched_yield();
}
file.close();
}
In this version of the program, a separate thread is spawned
for each file. First we call the function pthread_create() for
each file we encounter. A new thread is spawned with a pointer
to the function the thread should execute (in this case the same
function for all threads), called ParseFile(), which reads
lines from the respective files and increments the global variable
LINECOUNT. Several things are important here.
The main program is itself a thread. It is essential that we tell the main program to wait for the additional threads to join the main program before exiting, otherwise the main program will exit and kill all of the child threads immediately. Thread join-semantics are like wait-semantics for normal processes.
Each of the threads updates the same global variable. Suppose
now that two threads are running on different CPUs. It is
possible that both threads would try to alter the value
of the variable LINECOUNT simultaneously. This
is called a race condition and can lead
to unpredictable results. For this reason we use a mutex
to lock the variable while it is being updated. We shall discuss
this more in the next section.
A final point to note is the commented out lines in the
ParseFile() function. The call sched_yield()
tells a running thread to give itself up to the scheduler, so
that the next thread to be scheduled can run instead. This
function can be used to switch between several threads.
By calling this function after each line is read from the
files, we can spread the the CPU time evenly between each
thread. Actually, it is difficult to predict precisely
which threads will be scheduled and when, because the threads
in our program here are only a small number, compared to the
total number of threads waiting to be scheduled by the system.
The interaction with disk I/O can also have a complicated
effect on the scheduling. On a single CPU system, threads are
usually scheduled FCFS in a queue. If we yield after every
instruction, it has the effect of simulating round-robin
scheduling.
Early solaris systems had user-level threads only, which were called light weight processes. Since the kernel was single threaded, only one user-level thread could run at any given time.
To create a threaded process in solaris 1, one simply has to execute a LWP system call. The `lightweight processes library' then converts the normal process into a process descriptor plus a thread. Here is the simplest example
/********************************************************************/
/* */
/* Creating a light weight process in SunOS 4.1.3 */
/* */
/********************************************************************/
#include <lwp/lwp.h>
#include <lwp/stackdep.h>
#define MINSTACKSZ 1024
#define STACKSIZE 1000 + MINSTACKSZ
#define MAXPRIORITY 10
/*********************************************************************/
stkalign_t stack[STACKSIZE];
/*********************************************************************/
/* Zone 0 */
/*********************************************************************/
main ()
{ thread_t tid;
int task();
pod_setmaxpri(MAXPRIORITY); /* This becomes a lwp here */
lwp_create(&tid,task,MAXPRIORITY,0,STKTOP(stack),0);
printf("Done! - Now other threads can run...\n");
}
/*********************************************************************/
/* Zone 1 */
/*********************************************************************/
task ()
{
printf("Task: next thread after main()!\n");
}
Here is an example program containing several threads which wait for
each other.
/********************************************************************/
/* */
/* Creating a light weight process in sunos 4.1.3 (Solaris 1) */
/* */
/* Yielding to other processes */
/* */
/********************************************************************/
#include <lwp/lwp.h>
#include <lwp/stackdep.h>
#define MINSTACKSZ 1024
#define STACKCACHE 1000
#define STACKSIZE STACKCACHE + MINSTACKSZ
#define MAXPRIORITY 10
#define MINPRIORITY 1
/*********************************************************************/
stkalign_t stack[STACKSIZE];
/*********************************************************************/
/* Zone 0 */
/*********************************************************************/
main ()
{ thread_t tid_main;
thread_t tid_prog1;
thread_t tid_prog2;
int prog1(), prog2();
lwp_self(&tid_main); /* Get main's tid */
lwp_setstkcache(STACKCACHE,3); /* Make a cache for each prog */
lwp_create(&tid_prog1,prog1,MINPRIORITY,0,lwp_newstk(),0);
lwp_create(&tid_prog2,prog2,MINPRIORITY,0,lwp_newstk(),0);
printf("One ");
lwp_yield(THREADNULL);
printf("Four ");
lwp_yield(tid_prog2);
printf("Six ");
exit(0);
}
/*********************************************************************/
/* Zone 1,2.. */
/*********************************************************************/
prog1 ()
{
printf("Two ");
if (lwp_yield(THREADNULL) < 0)
{
lwp_perror("Bad yield");
return;
}
printf("Seven \n");
}
/*********************************************************************/
prog2 ()
{
printf("Three ");
lwp_yield(THREADNULL);
printf("Five ");
}
When two or more processes work on the same data simultaneously strange things can happen. We have already seen one example in the threaded file reader in previous section: when two parallel threads attempt to update the same variable simultaneously, the result is unpredictable. The value of the variable afterwards depends on which of the two threads was the last one to change the value. This is called a race condition. The value depends on which of the threads wins the race to update the variable.
What we need in a multitasking system is a way of making such situations predictable. This is called serialization.
It is not only threads which need to be synchronized. Suppose one user is running a script program and editing the program simultaneously. The script is read in line by line. During the execution of the script, the user adds four lines to the beginning of the file and saves the file. Suddenly, when the next line of the executing script gets read, the pointer to the next line points to the wrong location and it reads in the same line it already read in four lines ago! Everything in the program is suddenly shifted by four lines, without the process execting the script knowing about it.
This example (which can actually happen in the UNIX shell) may or may not turn out to be serious - clearly, in general, it can be quite catastrophic. It is a problem of synchronization on the part of the user and the filesystem4.1.
We must consider programs which share data.
The key idea in process synchronization is serialization. This means that we have to go to some pains to undo the work we have put into making an operating system perform several tasks in parallel. As we mentioned, in the case of print queues, parallelism is not always appropriate.
Synchronization is a large and difficult topic, so we shall only undertake to describe the problem and some of the principles involved here.
There are essentially two strategies to serializing processes in a multitasking environment.
The responsibility of serializing important operations falls on programmers. The OS cannot impose any restrictions on silly behaviour - it can only provide tools and mechanisms to assist the solution of the problem.
Another way of talking about serialization is to use the concept of mutual exclusion. We are interested in allowing only one process or thread access to shared data at any given time. To serialize access to these shared data, we have to exclude all processes except for one. Suppose two processes A and B are trying to access shared data, then: if A is modifying the data, B must be excluded from doing so; if B is modifying the data, A must be excluded from doing so. This is called mutual exclusion.
Mutual exclusion can be achieved by a system of locks. A mutual exclusion lock is colloquially called a mutex. You can see an example of mutex locking in the multithreaded file reader in the previous section. The idea is for each thread or process to try to obtain locked-access to shared data:
Get_Mutex(m); // Update shared data Release_Mutex(m);
The mutex variable is shared by all parties (e.g. a global variable).
This protocol is meant to ensure that only one process at a time
can get past the function Get_Mutex. All other processes
or threads are made to wait at the function Get_Mutex
until that one process calls Release_Mutex to release
the lock. A method for implementing this is discussed below.
Mutexes are a central part of multithreaded programming.
A simple example of a protocol solution, to the locking problem at the user level, is the so-called file-lock in UNIX. When write-access is required to a file, we try to obtain a lock by creating a lock-file with a special name. If another user or process has already obtained a lock, then the file is already in use, and we are denied permission to edit the file. If the file is free, a `lock' is placed on the file by creating the file lock. This indicates that the file now belongs to the new user. When the user has finished, the file lock is deleted, allowing others to use the file.
In most cases a lock is simply a text file. If we wanted to
edit a file blurb, the lock might be called
blurb.lock and contain the user identifier of the user currently
editing the file. If other users then try to access the file, they find
that the lock file exists and are denied access. When the user is
finished with the file, the lock is removed.
The same method of locks can also be used to prevent two instances of a program from starting up simultaneously. This is often used in mail programs such as the ELM mailer in UNIX, since it would be unwise to try to read and delete incoming mail with two instances of the mail program at the same time.
We can implement a lock very easily. Here is an example from UNIX in which the lock file contains the process identifier. This is useful because if something goes wrong and the editor crashes, the lock will not be removed. It is then possible to see that the process the lock referred to no longer exists and the lock can be safely removed.
//*********************************************************************
//
// Example of a program which uses a file lock to ensure
// that no one starts more than one copy of it.
//
//*********************************************************************
#include <iostream.h>
#include <fstream.h>
//**********************************************************************
// Include file
//**********************************************************************
extern "C" int getpid();
extern "C" void unlink(char *);
int Locked();
void RemoveLock();
const int true = 1;
const int false = 0;
const int exitstatus=1;
//**********************************************************************
// Main program
//**********************************************************************
main ()
{
if (Locked())
{
cout << "This program is already running!\n";
return exitstatus;
}
// Program here
RemoveLock();
}
//**********************************************************************
// Toolkit: locks
//**********************************************************************
Locked ()
{ ifstream lockfile;
int pid;
lockfile.open("/tmp/lockfile",ios::in);
if (lockfile)
{
return true;
}
lockfile.open("/tmp/lockfile",ios::out);
if (! lockfile)
{
cerr << "Cannot secure a lock!\n";
return true;
}
pid = getpid();
lockfile.out << pid;
lockfile.close();
return false;
}
//************************************************************************
void RemoveLock()
{
unlink("/tmp/lockfile");
}
If a user wishes to read a file, a non-exclusive lock is used. Other users can also get non-exclusive locks to read the file simultaneously, but when a non-exclusive lock is placed on a file, no user may write to it.
To write to a file, we must get an exclusive lock. When an exclusive lock is obtained, no other users can read or write to the file.
A critical section is a part of a program in which is it necessary to have exclusive access to shared data. Only one process or thread may be in a critical section at any one time.
In the past it was possible to implement this is by generalizing the idea of interrupt masks, as mentioned in chapter 2. By switching off interrupts (or more appropriately, by switching off the scheduler) a process can guarantee itself uninterrupted access to shared data. This method has drawbacks: i) masking interrupts can be dangerous - there is always the possibility that important interrupts will be missed, ii) it is not general enough in a multiprocessor environment, since interrupts will continue to be serviced by other processors - so all processors would have to be switched off; iii) it is too harsh. We only need to prevent two programs from being in their critical sections simultaneously if they share the same data. Programs A and B might share different data to programs C and D, so why should they wait for C and D?
The modern way of implementing a critical section is to use mutexes as we have described above. In 1981 G.L. Peterson discovered a simple algorithm for achieving mutual exclusion between two processes with PID equal to 0 or 1. The code goes like this:
int turn;
int interested[2];
void Get_Mutex (int pid)
{ int other;
other = 1 - pid;
interested[pid] = true;
turn = pid;
while (turn == pid && interested[other]) // Loop until no one
{ // else is interested
}
}
void Release_Mutex (int pid)
{
interested[pid] = false;
}
Where more processes are involved, some modifications are necessary to
this algorithm. The key to serialization here is that, if a second
process tries to obtain the mutex, when another already has it, it
will get caught in a loop, which does not terminate until the other
process has released the mutex. This solution is said to involve busy waiting--i.e. the program actively executes an empty loop,
wasting CPU cycles, rather than moving the process out of the
scheduling queue. This is also called a spin lock, since the
system `spins' on the loop while waiting.
Flags are similar in concept to locks. The idea is that two cooperating processes can synchronize their execution by sending very simple messages to each other. A typical behaviour is that one process decides to stop and wait until another process signals that it has arrived at a certain place.
For example, suppose we want to ensure that procedure1() in
process 1 gets executed before procedure2() in process 2.
// Process 1 // Process 2 procedure1(); wait(mysignal); signal(mysignal); procedure2(); ... ...
These operations are a special case of interprocess communication. A semaphore is a flag which can have a more general value than just true or false. A semaphore is an integer counting variable and is used to solve problems where there is competition between processes. The idea is that one part of a program tends to increment the semaphore while another part tends to decrement the semaphore. The value of the flag variable dictates whether a program will wait or continue, or whether something special will occur. There are many uses for semaphores and we shall not go into them here. A simple example is reading and writing via buffers, where we count how many items are in the buffer. When the buffer becomes full, the process which is filling it must be made to wait until space in the buffer is made available.
Some languages (like Modula) have special language class-environments for dealing with mutual exclusion. Such an environment is called a monitor.
These are the essential requirements for a deadlock:
where 
is waiting for a resource or signal from 
, is
waiting for 
... and 
is waiting for .
There are likewise three methods for handling deadlock situations:
Deadlock prevention requires a system overhead.
The simplest possibility for avoidance of deadlock is to introduce an
extra layer of software for requesting resources in addition to a
certain amount of accounting. Each time a new request is made, the
system analyses the allocation of resources before granting or
refusing the resource. The same applies for wait conditions.
The problem with this approach is that, if a process is not permitted to wait for another process - what should it do instead? At best the system would have to reject or terminate programs which could enter deadlock, returning an error condition.
Another method is the following. One might demand that all programs declare what resources they will need in advance. Similarly all wait conditions should be declared. The system could then analyse (and re-analyse each time a new process arrives) the resource allocation and pin-point possible problems.
The detection of deadlock conditions is also a system overhead. At regular intervals the system is required to examine the state of all processes and determine the interrelations between them. Since this is quite a performance burden, it is not surprising that most systems ignore deadlocks and expect users to write careful programs.
To recover from a deadlock, the system must either terminate one of the participants, and go on terminating them until the deadlock is cured, or repossess the resources which are causing the deadlock from some processes until the deadlock is cured. The latter method is somewhat dangerous since it can lead to incorrect program execution. Processes usually wait for a good reason, and any interruption of that reasoning could lead to incorrect execution. Termination is a safer alternative.
In this chapter we have considered the creation and scheduling of processes. Each process may be described by
Processes can be synchronized using semaphores or flags. Protocol constructions such as critical sections and monitors guarantee that shared data are not modified by more than one process at a time.
If a process has to wait for a condition which can never arise until it has finished waiting, then a deadlock is said to arise. The cause of deadlock waiting is often a resource which cannot be shared. Most operating systems do not try to prevent deadlocks, but leave the problem to user programs.
wait <number>' instructions.
Modify your program so that when one of the tasks reads an
instruction `wait 5', for instance, it waits for process number 5
to finish before it continues. The output of the kernel should show
this clearly. Hint: use a status variable which indicates whether
the process is `ready' or `waiting'.
Try to make your program as structured as possible. The aim is to write the clearest program, rather than the most efficient one. When presenting your results, give a listing of the output of each part and explain the main features briefly.
Together with the CPU, the physical memory (RAM) is the most important resource a computer has. The CPU chip has instructions to manipulate data only directly in memory, so all arithemtic and logic operations must take place in RAM.
Every byte in the memory has an address which ranges from zero up to a limit which is determined by the hardware (see below). Although bytes are numbered from zero upward, not every address is necessarily wired up to a memory chip. Some addresses may be reserved for
The physical address space consists of every possible address to which memory chips are connected.
A word is a small unit of memory, normally just a few bytes. The size of a word on any system is defined by the size of the registers in the CPU. This determines both the amount of memory a system can address and the way in which memory is used.
Up to about 1985, all CPUs had eight bit (1 byte) registers, except
for the program counter and address registers which were 16 bits. The
largest address which can be represented in a 16 bit number is
or 
bytes, and so these machines could not handle
more memory than this. Similarly, since the accumulator and index
registers were all 8 bits wide, no more than one byte could be
manipulated at a time. (This is why bytes have a special status.)
After that came a number of 16 bit processors with larger program counters. Nowadays most CPUs have 32 bit registers. The DEC alpha machines, together with the OSF/1 operating system are based on 64 bit technology. The possible address range and internal number representations are enormous. 64 bit versions of other versions of unix and NT are also starting to appear.
The size of the physical address space is limited by the size of the
address registers in the CPU. On early machines this memory was soon
exceeded and it was necessary to resort to tricks to add more memory.
Since it was not possible to address any more than the limit, these
machines temporarily switched out one bank of memory with
another. The new memory bank used the same addresses as the old, but
only one could be accessed at a time. This operation is called paging. A special hardware paging chip was used to switch between
banks, containing a register which could choose between banks of
memory.
Paging has obvious disadvantages - not all memory can be used at once and the method is seldom used nowadays since modern CPUs can address much larger memory spaces. As we shall see later, multi-user systems use paging to disk. Instead of switching between hardware banks of memeory, they copy the old contents to disk and reuse the memory which is already there for something else.
When a high level language program is compiled, it gets converted into machine code. In machine code there are no procedure names, or variable names. All references to data or program code are made by specifying the address at which they are to be found. This immediately begs the question: how do we know what the addresses will be? How do we know where the program is going to be located in memory?
On microcomputers, this is very straightforward. A program is compiled to run starting from some fixed address. The system defines a certain range of addresses which can be used by user programs (See figure 2.1). Whenever the program is loaded from disk, it is loaded into the memory at the same address, so that all of the addresses referred to in the program are correct every time.
A problem arises if the system supports several programs resident in memory simultaneously. Then it is possible that the addresses coded into one program will already be in use by another. In that case there are three possible options
Again there is a choice. When should this conversion take place?
 |
The concept of shared libraries lies somewhere in the grey zone between compiling and linking of programs and memory binding. We introduce it here for want of a better place. The advantages of shared libraries should be clearly apparent by the end of this section. On windows systems, shared libraries are called dynamically loaded libraries or dll's.
On older systems, when you compile a program, the linker attaches a copy of standard libraries to each program. Because of the nature of the linker, the whole library has to be copied even though perhaps only one function is required. Thus a simple program to print ``hello'' could be hundreds or thousands of kilobytes long! This wastes considerable amount of disk space, copying the same code for every program. When the program is loaded into memory, the whole library is loaded too, so it is also a waste of RAM.
The solution is to use a run-time linker, which only loads the shared library into RAM when one of the functions the library is needed. The advantages and disadvantages of this scheme are the following.
programs, which
now can share it. Also, the amount of RAM needed to support
programs is now considerably less.
 |
Keeping physical and logical addresses completely separate introduces a new level of abstraction to the memory concept. User programs know only about logical addresses. Logical addresses are mapped into real physical addresses, at some location which is completely transparent to the user, by means of a conversion table. The conversion can be assisted by hardware processors which are specially designed to deal with address mapping. This is much faster than a purely software solution (since the CPU itself must do the conversion work). The conversion is, at any rate, performed by the system and the user need know nothing about it.
The part of the system which performs the conversion (be it hardware or software) is called the memory management unit (MMU). The conversion table of addresses is kept for each process in its process control block (PCB) and mmust be downloaded into the MMU during context switching (this is one reason why context switching is expensive!). Each logical address sent to the MMU is checked in the following way:
One more question must be added to the above.
How is the translation performed in practice? To make the translation
of logical to phyical addresses practical, it is necessary to
coarse grain the memory. If every single byte-address were independently
converted, then two 
bit addresses would be required for each
byte-address in the table and
the storage space for the conversion table would be seven times bigger
than the memory of the system!
To get around this problem, we have to break up the memory into chunks of a certain size. Then we only need to map the start address of each block, which is much cheaper if the blocks are big enough. There are two schemes for coarse graining the memory in this way:
The disadvantage with this scheme is that either too much or too little memory might be allocated for the tasks. Moreover - if only a small part of the program is actually required in practice, then a large amount of memory is wasted and cannot be reused.
bits (this varies from system to system). The base address
of each page is then stored in the
conversion table (the length is known, since it is fixed). A unit of
logical memory is called a page, whereas a unit of physical
memory is called a frame. Apart from the difference in names, they
must of course have the same size.